package helper.base.math

import helper.base.A2LHM
import helper.base.LHMHelper.A2LHMExpand.makeA2LHM
import helper.base.LHMHelper.A2LHMExpand.touch
import helper.base.string.ToStrHelper.IToStr
import helper.base.string.ToStrHelper.TabStringUnit.Companion.makeTabStringUnit
import helper.base.string.ToStrHelper.toSBStr

// TreeHelper 包含用于管理树形结构中的父子关系的类
object TreeHelper {
    /**
     * T1ParentChildRelations 类提供了树形结构中父子关系的基础管理功能。
     *
     * 特点：
     * - 基础功能：允许添加单个或多个子节点到一个父节点，并能查询给定父节点的所有子节点。
     * - 数据结构：使用 A2LHM<E?, HashSet<E>> 存储父节点到其子节点的映射，
     *   其中 E 是元素类型，允许快速查找给定父节点的所有子节点。
     * - 适用场景：适合需要管理和查询父子关系，但不需要反向查询（从子节点找到父节点）的场景。
     */
    open class T1HierarchyStructure<E>(
        // 父节点到其子节点的映射
        val aParentChildrenLHM: A2LHM<E?, HashSet<E>> = makeA2LHM(),
    ) : IToStr { // 实现 IToStr 接口以提供字符串表示的功能
        // 伴生对象提供静态方法来创建 T1ParentChildRelations 实例
        companion object {
            fun <E> makeT1HierarchyStructure(
                pParentChildrenLHM: A2LHM<E?, HashSet<E>> = makeA2LHM(),
            ): T1HierarchyStructure<E> {
                return T1HierarchyStructure(pParentChildrenLHM)
            }
        }

        // 提供一个方法将父子关系映射转换为字符串表示，用于调试或日志
        override fun toStr(tabNum: Int): String {
            val sb = StringBuilder() // 创建字符串构建器
            val tsu = makeTabStringUnit(tabNum) // 获取制表符单位
            this.aParentChildrenLHM.touch { a1, a2 ->
                a1.toSBStr(sb, tsu, 0) // 将父节点转换为字符串
                a2.forEach {
                    it.toSBStr(sb, tsu, 1) // 将每个子节点转换为字符串
                }
            }
            return sb.toString()
        }

        // 添加单个父子关系
        open fun addRelation(parent: E?, child: E) {
            aParentChildrenLHM.getOrPut(parent) {
                linkedSetOf()
            }.add(child)
        }

        // 添加多个子节点到同一个父节点
        fun addRelations(parent: E?, children: List<E>) {
            children.forEach { child ->
                addRelation(parent, child)
            }
        }

        // 使用 vararg 参数添加多个子节点，内部转换为 List 调用
        fun addRelations(parent: E?, vararg children: E) {
            addRelations(parent, children.toList())
        }

        // 查找指定父节点的所有子节点
        fun findChildren(parent: E?): HashSet<E>? {
            return aParentChildrenLHM[parent]
        }

        // 重写 toString 方法以提供简化的字符串表示
        override fun toString(): String {
            val sb = StringBuilder() // 创建字符串构建器
            this.aParentChildrenLHM.forEach { (t, u) ->
                sb.append("${t}=${u}\n") // 将每个父子关系映射转换为字符串
            }
            return sb.toString().trim()
        }
    }

    /**
     * T2ParentChildRelations 类扩展了 T1ParentChildRelations，提供了更高级的功能。
     *
     * 特点：
     * - 扩展功能：除了继承基础类的所有功能外，支持反向查询，即可以从子节点查询其父节点。
     * - 额外的数据结构：内部额外维护了一个 A2LHM<E, E?> 映射，用于存储子节点到父节点的关系，
     *   支持从子节点查找父节点的功能。
     * - 祖先查询：提供了方法 findAllAncestors，用于查找一组节点的所有祖先节点，适用于处理复杂的树形结构查询。
     * - 适用场景：适合需要双向查询父子关系和查询节点祖先的更复杂应用场景。
     */
    class T2HierarchyStructure<E> : T1HierarchyStructure<E>() {
        // 存储子节点到父节点的映射
        private val pChildParentLHM = A2LHM<E, E?>()

        // 伴生对象提供静态方法来创建 T2ParentChildRelations 实例
        companion object {
            fun <E> makeT2ParentChildRelations(): T2HierarchyStructure<E> {
                return T2HierarchyStructure()
            }
        }

        // 添加单个父子关系，同时更新子到父的映射
        override fun addRelation(parent: E?, child: E) {
            super.addRelation(parent, child)
            pChildParentLHM[child] = parent
        }

        // 查找指定子节点的父节点
        fun findParent(child: E): E? {
            return pChildParentLHM[child]
        }

        /**
         * 查找给定激活位置的所有祖先节点。
         *
         * 该方法遍历激活位置列表 `activatedLocations`，对于每个位置，沿父节点链向上遍历，
         * 直到找不到更多的父节点为止。这个过程会收集每个位置及其所有祖先节点，并将它们存储
         * 在一个新的父子关系映射中。
         *
         * 特点：
         * - 动态构建父子关系映射：对于激活位置及其所有祖先，构建一个新的父子关系映射。
         * - 祖先的重复利用：如果多个激活位置共享相同的祖先节点，这些祖先节点只会被添加一次。
         * - 返回类型：返回一个 `T1ParentChildRelations<E>` 实例，其中包含了所有激活位置及其祖先的完整父子关系。
         *
         * 参数：
         * - `activatedLocations`：一个 `ArrayList<E>`，包含需要查询祖先的激活位置列表。
         *
         * 返回值：
         * - 返回一个 `T1ParentChildRelations<E>` 实例，它包含了一个 `A2LHM<E?, LinkedHashSet<E>>`，
         *   映射了从父节点到子节点（激活位置及其祖先）的关系。
         *
         * 适用场景：
         * - 当需要在树形结构中快速找出一组节点及其所有祖先节点的关系时，特别有用。
         * - 在处理依赖关系、继承链、或者任何需要追溯源头的场景中非常实用。
         */
        fun findAllAncestors(activatedLocations: ArrayList<E>): T1HierarchyStructure<E> {
            val re = makeT1HierarchyStructure<E>()

            activatedLocations.forEach { location ->
                var currentLocation: E? = location
                while (currentLocation != null) { // 遍历查找所有祖先
                    val parent = pChildParentLHM[currentLocation]
                    re.addRelation(parent, currentLocation)
                    currentLocation = parent
                }
            }

            return re
        }
    }
}
